
// 二叉搜索树搜索方法
public boolean search(TreeNode root, int val) {
	TreeNode cur = root;
	if (root == null) return false;
	while (cur != null) {
		if (cur.val < val) {
			cur = cur.left;
		} else if(cur.val > val) {
			cur = cur.right;
		} else {
			return true;
		}
	}
	return false;
}

// 二叉搜索树插入方法
public boolean insert(TreeNode root, int val) {
	TreeNode cur = root;
	TreeNode parent = null;
	TreeNode node = new TreeNode(val);
	
	if (root == null) {
		root = node;
	}
	
	while (cur != null) {
		if (val < cur.val) {
			parent = cur;
			cur = cur.left;
		} else if(val > cur.val) {
			parent = cur;
			cur = cur.right;
		} else {
			// 该二叉树已经有该元素了
			return false;
		}
	}
	
	// 出了 while 循环之后，cur 已经到了值为 val 的节点应该插入的位置 
	// parent 是该节点的父亲节点
	if(val < parent.val) {
		parent.left = node;
	} else {
		parent.right = node;
	}
	return true;
}


// 二叉搜索树删除方法
public void remove(TreeNode root, int val) {
	TreeNode cur = root;
	TreeNode parent = null;
	while (cur != null) {
		// 查找
		if (val < cur.val) {
			parent = cur;
			cur = cur.left;
		} else if(val > cur.val) {
			parent = cur;
			cur = cur.right;
		} else {
			//删除
			removeNode(root,parent, cur)
			return;
		}
	}
}

private void removeNode(TreeNode root, TreeNode parent, TreeNode cur) {
	if (cur.left == null) {
		if (cur == root) {
			root = cur.right;
		} else if(cur == parent.left) {
			parent.left = cur.right;
		} else if(cur == parent.right){
			parent.right = cur.right;
		}
	} else if(cur.right == null) {
		if (cur == root) {
			root = cur.left;
		} else if(cur == parent.left) {
			parent.left = cur.left;
		} else if(cur == parent.right) {
			parent.right = cur.left;
		}
	} else if(cur.left != null && cur.right != null) {
		// 替代法
		TreeNode targetParent = cur;
		TreeNode target = cur.right;
		while (target.left != null) {
			targetParent = target;
			target = target.left;
		}
		// 此时 target 指向要删除节点的右子树的最左侧子树
		// 覆盖
		cur.val = target.val;
		// 判断要删除的节点的右子树是否有左子树
		if(targetParent.left == target) {
			// 正常情况下的删除
			targetParent.left = target.right;
		}
		if(targetParent.right == target) {
			targetParent.right = target.right;
		}
	}
}

// 解决哈希冲突 -- 开散列
public void hashBuck() {
	
	static class Node {
		public int key;
		public int value;
		public Node next;
		public Node(int key, int value) {
			this.key = key;
			this.value = value;
		}
	}
	public Node[] array;
	public int usedSize;
	
	public hashBuck() {
		array = new Node[10];
	}
	
	
	public void put(int key, int val) {
		// 根据 key 计算下标
		int index = key % array.length;
		
		// 定义一个 cur 用来遍历该索引下的链表
		// 确认是否存在当前的 key
		Node cur = array[index];
		while (cur != null) {
			if (key == cur.key) {
				cur.val = val; // 如果存在，则覆盖 val
				return;
			}
			cur = cur.next;
		}
		
		// 如果没有 key 则使用头插法插入
		Node node = new Node(key,val);
		node.next = array[index];
		array[index] = node;
		usedSize++;
		
		// 添加完成后，判断负载因子，如果负载因子大于 0.75 对散列表扩容
		if (loadFactor() >= 0.75) {
			resize();
		}
	}
	
	private double loadFactor() {
		return usedSize * 1.0 / array.length;
	}
	
	// 在 resize 方法中，对散列表进行扩容
	// 扩容后，由于 array.length 发生了变化
	// 所以因此计算的 index 也会发生变化
	// 因此需要重新哈希计算
	private void resize() {
		Node[] tmpArr = new Node[array.length * 2];
		
		// 遍历之前的数据的元素
		for (int i == 0; i < array.length; i++) {
			Node cur = array[i];
			while (cur != null) {
				Node curNext = cur.next;
				int newIndex = cur.key % tmpArr.length;
				
				// 头插法插入元素
				cur.next = tmpArr[index];
				tmpArr[index] = cur;
				
				cur = curNext;
			}
		}
	}
	
	public void get(int key) {
		int index = key % array.length;
		Node cur = array[index];
		while (cur != null) {
			if (key == cur.key) {
				return cur.val;
			}
			cur = cur.next;
		}
		return -1;
	}
	
}


class Person {
	String id;
	public Person(String id) {
		this.id = id;
	}
	@Override
	public int hashCode() {
		return Objects.hashCode(id);
	}
}

public void HashBuck2<K,V>{
	static class Node<K,V> {
		public K key;
		public V value;
		public Node next;
		public Node(K key, V value){
			this.key = key;
			this.value = value;
		}
	}
	
	public Node<K,V>[] array;
	public int usedSize;
	
	public HashBuck2() {
		array = (Node<K,V>[]))new Node[10];
	}
	
	public void put(K key, V value) {
		int hash = key.hashCode();
		int index = hash % array.length;
		
		Node cur = array[index];
		
		while (cur != null) {
			if(key == cur.key) {
				cur.val = val;
				return;
			}
			cur = cur.next;
		}
		
		Node node = new Node<>(key,val);
		node.next = array[index];
		array[index] = node;
		usedSize++;
	}
	
	public V get(K key) {
		int hash = key.hashCode();
		int index = hash % array.length;
		
		Node cur = array[index];
		while (cur != null) {
			if (key == cur.key) {
				return cur.val;
			}
			cur = cur.next;
		}
		return null;
	}
}


/**
 只出现一次的数字。给定一个数组，除了某个元素只出现过一次以外，其余元素均出现两次
 找到那个只出现了一次的元素
*/
public int singleNumber(int[] nums) {
	
	Set<Integer> set = new HashSet<>();
	for(int i = 0; i < nums.length; i++) {
		if (set.contains(nums[i])) {
			set.remove(nums[i]);
		} else {
			set.add(nums[i]);
		}
	}
	return set.iterator().next();
}

/**
深拷贝含有随机指针的链表
*/
public Node copyRandomList(Node head) {
	HashMap<Node,Node> map = new HashMap<>();
	Node cur = head;
	while (cur != null) {
		Node node = new Node(cur.val);
		map.put(cur,node);
		cur = cur.next;
	}
	cur = head;
	while (cur != null) {
		map.get(cur).next = map.get(cur.next);
		map.get(cur).random = map.get(cur.random);
		cur = cur.next;
	}
	
	return map.get(head);
}

/**
 石头里面挑宝石
*/
public int numJewelsInStones(String jewels, String stones) {
	HashSet<Character> set = new HashSet<>();
	
	// 将宝石存放进 set 集合中
	for(int i = 0; i < jewels.length(); i++) {
		set.add(jewels.charAt(i));
	}
	
	int count = 0;
	for(int i = 0; i < stones.length();i++) {
		if(set.contains(stones.charAt(i))) {
			count++;
		}
	}
	return count;
}


/**
旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字
请你列出肯定坏掉的那些键。
输入在2行中分别给出应该输入的文字、以及实际被输入的文字。
按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。
*/

public void func(String str1, String str2) {
	
	Set<Character> set1 = new HashSet<>();
	for(char ch : str2.toUpperCase().toCharArray()) {
		set1.add(ch);
	}
	Set<Character> set2 = new HashSet<>();
	for(char ch : str1.toUpperCase().toCharArray()) {
		if (!set1.contains(ch) && !set2.contains(ch)){
			System.out.print(ch);
			set2.add(ch);
		}
	}
}

public List<String> topKFrequent(String[] words, int k) {
	
	// 1. 统计每个单词出现的次数
	HashMap<String, Integer> map = new HashMap<>();
	for (String word : words) {
		if (map.get(word) == null) {
			map.put(word,1);
		} else {
			int value = map.get(word);
			map.put(word, value + 1);
		}
	}
	
	// 2. 建立小根堆，指定比较的方式
	PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueueo<>(
	new Comparator<Map.Entry<String,Integer>>(){
		public int compare(Map.Entry<String,Integer> o1, Map.Entry<String, Integer> o2) {
			if (o1.getValue().compareTo(o2.getValue())) {
				return o2.getKey().compareTo(o1.getKey());
			}
			return o1.getValue() - o2.getValue();
		}
	});
		
	// 3. 遍历 map 调整优先级队列
	for(Map.Entry<String, Integer> enrty : map.entrySet()) {
		if (minHeap.size() < k) {
			minHeap.offer(entry);
		} else {
			Map.Entry<String. Integer> top = minHeap.peek();
			// 如果当前单词出现的次数相同
			if （top.getValue().compareTo(entry.getValue()) == 0) {
				// 让字母顺序小的进来
				if(top.getKey().compareTo(entry.getKey()) > 0) {
					minHeap.poll();
					minHeap.offer(enrty);
				}
			} else {
				if(top.getValue().compareTo(entry.getValue()) < 0) {
					minHeap.poll();
					minHeap.offer(entry);
				}
			}
		}
	}
	
	List<String> ret = new Array<>();
	for (int i = 0; i < k; i++) {
		Map.Entry<String, Integer> top = minHeap.poll();
		ret.add(top.getKey());
	}
	
	Collections.reverse(ret);
	
	return ret;
}
